/*MiniChessTeamAwesome © 2012 by Philipp Lange, Markus Stecher (MIT License)*/

import java.io.*;
import java.util.ArrayList;

public class State {

	/* test class */
	public static void main(String[] args) throws IOException {
		// State test=new State(System.in);
		State test = new State();
		ArrayList<Move> m = test.moves();
		System.out.println(m.size());
		System.out.println(m.get(0).toString());
		System.out.println(test.toString());
	}

	public char board[][] = new char[6][5];
	public char onMove;
	public int moveNum;
	public static long negaMaxCount;
	public static long timeLimit;

	/* basic board setup */
	char[][] initBoard = { { 'k', 'q', 'b', 'n', 'r' },
			{ 'p', 'p', 'p', 'p', 'p' }, { '.', '.', '.', '.', '.' },
			{ '.', '.', '.', '.', '.' }, { 'P', 'P', 'P', 'P', 'P' },
			{ 'R', 'N', 'B', 'Q', 'K' } };

	public static Move m0;

	/*
	 * {'.','.','.','.','.'}, {'.','.','.','.','.'}, {'.','.','.','.','.'},
	 * {'.','.','.','.','.'}, {'.','.','.','.','.'}, {'.','.','.','.','.'}
	 * 
	 * {'k','q','b','n','r'}, {'p','p','p','p','p'}, {'.','.','.','.','.'},
	 * {'.','.','.','.','.'}, {'P','P','P','P','P'}, {'R','N','B','Q','K'}
	 */

	/* constructor for new state */
	public State() {
		board = new char[6][5];
		for (int r = 0; r < 6; r++)
			for (int c = 0; c < 5; c++)
				board[r][c] = initBoard[r][c];
		onMove = 'W';
		moveNum = 1;
	}

	/* constructor to setup state from string */
	public State(String desc) {
		String[] split = desc.split(" ");
		moveNum = Integer.parseInt(split[0]);
		onMove = split[1].charAt(0);
		split = desc.split("\n");
		for (int r = 1; r < 7; r++) {
			char buffer[] = split[r].toCharArray();
			for (int c = 0; c < 5; c++) {
				board[r-1][c] = buffer[c];
			}
		}
	}

	/* constructor to setup state from stream */
	public State(InputStream stream) throws IOException {
		InputStreamReader in = new InputStreamReader(stream);
		BufferedReader bin = new BufferedReader(in);
		String string = bin.readLine();
		String[] stringarray = string.split(" ");

		moveNum = Integer.parseInt(stringarray[0]);
		onMove = stringarray[1].charAt(0);

		for (int r = 0; r < 6; r++) {
			char[] chararray = bin.readLine().toCharArray();
			for (int c = 0; c < 5; c++) {
				board[r][c] = chararray[c];
			}
		}
	}

	/* output state as a String */
	public String toString() {
		String output;
		output = moveNum + " " + onMove;
		for (int r = 0; r < 6; r++) {
			output = output + "\n";
			for (int c = 0; c < 5; c++) {
				output = output + board[r][c];
			}
		}
		return output;
	}

	/* output state as a stream */
	public void print(OutputStream stream) throws IOException {
		OutputStreamWriter out = new OutputStreamWriter(stream);
		BufferedWriter bout = new BufferedWriter(out);
		bout.write(moveNum + " " + onMove);
		for (int r = 0; r < 6; r++) {
			bout.newLine();
			for (int c = 0; c < 5; c++) {
				bout.write(board[r][c]);
			}
		}
	}

	/* do a move from square1 to square2 */
	public char move(Square s1, Square s2) {
		char out = '?';
		if (board[s2.r][s2.c] == 'k') {
			out = 'W';
		} else if (board[s2.r][s2.c] == 'K') {
			out = 'B';
		}
		board[s2.r][s2.c] = board[s1.r][s1.c];
		board[s1.r][s1.c] = '.';
		if (onMove == 'B') {
			onMove = 'W';
			moveNum++;
			if (moveNum > 40) {
				out = '=';
			}
		} else if (onMove == 'W') {
			onMove = 'B';
		}
		/* promote prawn when he reaches other side */
		if (s2.r == 0 || s2.r == 5) {
			if (board[s2.r][s2.c] == 'p') {
				board[s2.r][s2.c] = 'q';
			} else if (board[s2.r][s2.c] == 'P') {
				board[s2.r][s2.c] = 'Q';
			}
		}
		return out;
	}

	/* do a move from Move Object */
	public char move(Move m) {
		return move(m.fromSquare, m.toSquare);
	}

	/* do a move by inputting a String (e.g. a2-a3) */
	public char move(String str) {
		Square Sq1 = new Square(str.substring(0, 2));
		Square Sq2 = new Square(str.substring(3, 5));
		return move(Sq1, Sq2);
	}

	/* human move checks if move is legal and executes */
	public char human_move(String str) {
		ArrayList<Move> moves = moves();
		for (Move move : moves) {
			if (move.toString().equals(str))
				return move(str);
		}
		return 'E';
	}

	/* get all pieces you can move */
	public ArrayList<Square> pieces() {
		ArrayList<Square> squares = new ArrayList<Square>();
		for (int r = 0; r < 6; r++) {
			for (int c = 0; c < 5; c++) {
				if (board[r][c] != '.'
						&& ((onMove == 'W' && 'A' <= board[r][c] && board[r][c] <= 'Z') || (onMove == 'B'
								&& 'a' <= board[r][c] && board[r][c] <= 'z'))) {
					squares.add(new Square(r, c));
				}
			}
		}
		return squares;
	}

	/* returns the color of the given piece */
	public char isColor(int r, int c) {
		if (board[r][c] == '.')
			return '.';
		if ('A' <= board[r][c] && board[r][c] <= 'Z')
			return 'W';
		return 'B';
	}

	public char isColor(Square square) {
		return isColor(square.r, square.c);
	}

	/* movescan with given direction */
	public ArrayList<Move> movescan(Square fromSquare, int dr, int dc,
			Boolean stopShort, Boolean capture) {
		int r = fromSquare.r;
		int c = fromSquare.c;
		char color = onMove;
		ArrayList<Move> moves = new ArrayList<Move>();
		do {
			r = r + dr;
			c = c + dc;
			if (r < 0 || r > 5 || c < 0 || c > 4) {
				break;
			}
			if (board[r][c] != '.') {
				if (color == isColor(r, c)) {
					break;
				}
				if (capture == false) {
					break;
				}
				stopShort = true;
			}
			moves.add(new Move(new Square(fromSquare.r, fromSquare.c), new Square(r, c)));
		} while (stopShort == false);
		return moves;
	}

	/* default capture=true */
	public ArrayList<Move> movescan(Square fromSquare, int dr, int dc,
			Boolean stopShort) {
		return movescan(fromSquare, dr, dc, stopShort, true);
	}

	/* default stopshort=false, capture=true */
	public ArrayList<Move> movescan(Square fromSquare, int dr, int dc) {
		return movescan(fromSquare, dr, dc, false, true);
	}

	/* creates an array list with all possible moves for this state*/
	public ArrayList<Move> moves() {
		ArrayList<Move> moves = new ArrayList<Move>();
		ArrayList<Square> pieces = pieces();
		for (Square piece : pieces) {
			int r = piece.r;
			int c = piece.c;
			Boolean stopShort = false;
			Boolean capture = true;
			switch (board[r][c]) {
			case 'K':
			case 'k':
				stopShort = true;
			case 'Q':
			case 'q':
				for (int dr = -1; dr < 2; dr++) {
					for (int dc = -1; dc < 2; dc++) {
						if (dr == 0 && dc == 0)
							continue;
						moves.addAll(movescan(piece, dr, dc, stopShort, capture));
					}
				}
				break;
			case 'R':
			case 'r':
			case 'B':
			case 'b':
				int dr = 1;
				int dc = 0;
				int buffer;
				if (board[r][c] == 'b' || board[r][c] == 'B') {
					stopShort = true;
					capture = false;
				}
				for (int i = 1; i < 5; i++) {
					moves.addAll(movescan(piece, dr, dc, stopShort, capture));
					buffer = dr;
					dr = dc;
					dc = buffer;
					dc = -dc;
				}
				if (board[r][c] == 'b' || board[r][c] == 'B') {
					dr = 1;
					dc = 1;
					stopShort = false;
					capture = true;
					for (int i = 1; i < 5; i++) {
						moves.addAll(movescan(piece, dr, dc, stopShort, capture));
						buffer = dr;
						dr = dc;
						dc = buffer;
						dc = -dc;
					}
				}
				break;
			case 'N':
			case 'n':
				stopShort = true;
				dr = 1;
				dc = 2;
				for (int i = 1; i < 5; i++) {
					moves.addAll(movescan(piece, dr, dc, stopShort));
					buffer = dr;
					dr = dc;
					dc = buffer;
					dc = -dc;
				}
				dr = -1;
				dc = 2;
				for (int i = 1; i < 5; i++) {
					moves.addAll(movescan(piece, dr, dc, stopShort));
					buffer = dr;
					dr = dc;
					dc = buffer;
					dc = -dc;
				}
				break;
			case 'P':
			case 'p':
				int dir = -1;
				if ('B' == isColor(r, c))
					dir = 1;
				stopShort = true;
				ArrayList<Move> m = movescan(piece, dir, -1, stopShort);
				if (m.size() == 1 && '.' != isColor(m.get(0).toSquare))
					moves.addAll(m);
				m = movescan(piece, dir, 1, stopShort);
				if (m.size() == 1 && '.' != isColor(m.get(0).toSquare))
					moves.addAll(m);
				capture = false;
				moves.addAll(movescan(piece, dir, 0, stopShort, capture));
				break;
			}
		}
		return moves;
	}

	/*returns the value of this state*/
	public int stateValue() {
		int stateValue = 0;

		for (int r = 0; r < 6; r++) {
			for (int c = 0; c < 5; c++) {
				stateValue += pieceValue(r, c);
			}
		}
		if (stateValue <= -5000)
			return -10000;
		if (stateValue >= 5000)
			return 10000;
		return stateValue;
	}

	/*returns the value of a given piece on the board*/
	public int pieceValue(int r, int c) {
		int value = 1;
		if (isColor(r, c) == '.')
			return 0;
		if (onMove != isColor(r, c))
			value = -1;
		switch (board[r][c]) {
		case 'p':
			if(r!=1)
				value *= (130+r-1);
			else
				value *= 100;
			break;
		case 'P':
			if(r!=4)
				value *= (130+4-r);
			else
				value *= 100;
			break;
		case 'b':
			if(r!=0)
				value *= 310;
			else
				value *= 300;
			break;
		case 'B':
			if(r!=5)
				value *= 310;
			else
				value *= 300;
			break;
		case 'n':
			if(r!=0)
				value *= 160;
			else
				value *= 150;
			break;
		case 'N':
			if(r!=5)
				value *= 160;
			else
				value *= 150;
			break;
		case 'r':
		case 'R':
			value *= 400;
			break;
		case 'q':
		case 'Q':
			value *= 600;
			break;
		case 'k':
		case 'K':
			value *= 10000;
			break;
		}
		return value;
	}

	/*negaMax algorithm*/
	public int negaMax(int d, Boolean top, int a0, int b0){
		if(0<=negaMaxCount--){
			negaMaxCount=1000;
			if(System.currentTimeMillis()>=timeLimit){
				return -10000;
			}
		}
		int value=stateValue();
		if (d <= 0 || value >= 10000 || value <= -10000) {
			return value;
		}
		ArrayList<Move> movelist = moves();
		State sNew = new State(toString());
		Move m = movelist.get(0);
		sNew.move(m);
		int vNew = -sNew.negaMax(d - 1, false, -b0, -a0);
		if (top)
			m0 = m;
		for (int i = 1; i < movelist.size() ; i++) {
			sNew = new State(toString());
			m = movelist.get(i);
			sNew.move(m);
			int v = -sNew.negaMax(d - 1, false, -b0, -a0);
			if (v >= b0)
				return v;
			if(v > a0)
				a0 = v;
			if (v > vNew) {
				vNew = v;
				if (top)
					m0 = m;
			}
		}
		return vNew;
	}

	/*returns a random move for this state*/
	public Move getRandomMove(){
		ArrayList<Move> m=moves();
		int i = (int) Math.round(m.size()*Math.random())-1;
		if(i<0)
			i=0;
		return m.get(i);
	}

	/*returns a move that captures the most valuable piece*/
	public Move getGreedyMove(){
		timeLimit=Long.MAX_VALUE;
		negaMax(1, true, Integer.MAX_VALUE, Integer.MIN_VALUE);
		return m0;
	}

	/*returns the "best" move using negamax(3, true) for this state*/
	public Move getGoodMove(){
		timeLimit=Long.MAX_VALUE;
		negaMax(3, true, Integer.MAX_VALUE, Integer.MIN_VALUE);
		return m0;
	}

	/*returns the best move using negamax with iterative deepening assuming game time is 5:00*/
	public Move getBetterMove(){
		negaMaxCount=1000;
		timeLimit=System.currentTimeMillis()+6750;
		ArrayList<Move> moves=new ArrayList<Move>();
		for(int d=3; ; d++){
			negaMax(d, true, -100000, 100000);
			moves.add(m0);
			if(System.currentTimeMillis()>=timeLimit){
				System.out.println("Depth: " + (d-1));
				return moves.get(d-4);
			}
		}
	}

}// endclass State
